/**
 * 41题代码
*/

#define MAX_SIZE 100
#include<stdbool.h>
#include<stdio.h>
typedef struct 
{
    int SqBiTNode[MAX_SIZE];//存储的数组
    int ElemNum; //树的节点个数
}SqBiTreet;

//测试数据
SqBiTreet T1;
SqBiTreet T2;

/**
 * 判断当前树是否为二叉搜索树
 * 基本思想：二叉搜索树的特征就是根节点的左子树所有节点都小于根节点，右子树的所有节点都大于根节点
 * 直接做法就是对于每个节点都查找左子树和右子树看里面有没有不合格的节点，但是这样的时间复杂度太大了
 * 注意：二叉搜索树，中序遍历的的结果是升序的，可以利用这一性质
 * 使用val（初始为-1）记录中序遍历过程中节点的最大值，当遍历的节点小于val时，说明不符合二叉搜索树特征，否则更新val
 * 为当前节点的值
 * 
 * @return int 是则返回true，否则返回false
 */
bool isBiSearchTree(SqBiTreet t,int root,int *val){
    if(root<t.ElemNum&&t.SqBiTNode[root]!=-1){//root是根节点，也是当前访问的节点，要保证不为空且小于数组长度
        if(!isBiSearchTree(t,2*root+1,val)){ //左递归
            return false;
        }
        if(t.SqBiTNode[root]<=*val) {//当前节点，不符合搜索树的特征，返回false
            return false;
        }
        *val=t.SqBiTNode[root];//符合条件，就赋值
        if(!isBiSearchTree(t,2*root+2,val)){ // 右递归
            return false;
        }
    }
    return true;//遍历完之后还没有false，则要输出true
}
int val=-1;
int main(void){
    int temp1[]={40,25,60,-1,30,-1,80,-1,-1,27};
    int temp1_size=10;
    for(int i=0;i<temp1_size;i++){
        T1.SqBiTNode[i]=temp1[i];
    }
    T1.ElemNum=temp1_size;
    printf("是否为二叉搜索树：%d\n",isBiSearchTree(T1,0,&val));
    return 0;
}